Last time, we defined the following functions

• \(\pi(a \mid s)\), our policy
• \(v_\pi(s)\), the state value function
• \(v_\pi(s, a)\), the state value function

and mentioned that we want to maximize the expectation of the discounted reward,

\[ G^{(\pi)}_t = \sum_{k=t+1}^T \gamma^{k - {t + 1}} R_k \]

Recall the example from the previous chapter with \(3\) states and \(2\) actions.

Now, let our policy \(\pi\) and suppose that we are on \(s_0\). If we knew \(v_\pi(s)\) for \(s \ne s_0\), then how shall we find \(v_\pi(s_0)\)?

This is a simple application of the expectation formula

\[ \mathbb{E}[X] = \sum_{x \in S_X} xf(x) \]

In particular,

\[ v_\pi(s_0) = \sum_r r \cdot p(r \mid s_0, \pi(s_0)) + \gamma \sum_{s} v_\pi(s) p(s \mid s_0, \pi(s_0)) \]

or that we find the expected reward with the discounted expected next reward.

Similarly, we find the values for \(v_\pi(s_0, a_0)\).

\begin{align} v_\pi(s_0) &= \sum_a \pi(a \mid s_0) v_\pi(s_0, a) \\ v_\pi(s_0, a_0) &= \sum_{s, r} p(s, r \mid s_0, a_0)[r + \gamma v_\pi(s)] \end{align}

Finally, we achieve the Bellman equations implicitely with a substitution, which describes \(v_\pi(s)\) and \(v_\pi(s, a)\).

We define an optimal policy \(\pi_*\) as the policy that maximizes reward. In particular,

\begin{align} v_*(s) &= \mathrm{max}_\pi v_\pi(s) = \mathrm{max}_a v_*(s, a) \\ v_*(s, a) &= \mathrm{max}_\pi v_\pi(s, a) \end{align}

With all this setup, we can describe an algorithm (sequential policy iteration) to find the optimal policies \(\pi_*\), consisting of two subroutines.

First, we describe policy evaluation, computing all value functions for a given \(\pi\) (by iterating until equilibrium). Supposing we have an initial distribution of \(v_\pi(s, a)\) and \(v_\pi(s)\), we shall apply the Bellman equation, updating all values. Next, we describe policy iteration, which updates each policy \(\pi\) to take the argmax of the value functions.

The generalized policy iteration (GPI) theorem states that this process converges to an optimal policy. It further asserts that this algorithm has redundant steps. For example, value iteration instead loops over all action pairs, rather than that specified by a policy.

A python implementation of the Gambler's Problem, described in Sutton-Bartol Example 4.3

Home 1 2 3 4(b) 5 6 Next